1. Field of the Invention
The present invention relates to data coding method and device, data decoding method and device, and data supply medium, and particularly to data coding method and device, data decoding method and device, and data supply medium which are effectively used for cases where video data, audio data or other digital data are recorded in a recording medium such as a magnetic disc, a magnetic tape, an optical disc, a magnet optical disc, a phase-variation disc or the like and these data are reproduced from the recording medium.
2. Description of the Related Art
When video data and audio data are digitally recorded or reproduced into or from a recording medium such as a magnetic disc, an optical disc, a magnet optical disc, a magnetic tape or the like, it is required that the data can be recorded in as high density as possible and with high reliability. It is known that a PRML (Partial Response signaling with Maximum Likelihood detection) system which is implemented by combining a partial response system and a maximum likelihood decoding (detection) system is preferably used in order to satisfy the above requirement. According to PRML, data can be recorded in higher density and with higher reliability. In general, a partial response (1,1) or a partial response (1,0,xe2x88x921) is used for the recording of digital data, and Viterbi decoding (Viterbi detection) is usually used for the maximum likelihood detection system.
There has been known a technique in which by combining the partial response system with the coding technique, the squared free euclidean distance d2free is increased and SNR (Signal to Noise Ratio) is enhanced on the output of a partial response channel, whereby data can be recorded in high density and with high reliability. This technique is called as TCPR (Trellis Coded Partial Response), and a code produced by this technique is called as a Trellis code.
Here, the squared free euclidean distance d2free is the minimum euclidean distance between two different paths which start from a common state and end to a common state on a Trellis diagram representing the output sequence of the partial response channel (hereinafter referred to as Detector Trellis. The Viterbi detection is carried out on the basis of the Detector Trellis). The starting and ending states may be different from each other.
For example, in the partial response (1,0,xe2x88x921) (hereinafter abbreviated as PR4), if d2free of the conventional bit-by-bit detection system is set to 1, d2free can be set to 2 by performing the Viterbi detection (PR4ML). Here, PR4ML means a combination system of PR4 and the maximum likelihood decoding (Viterbi detection). SNR can be more enhanced as the value of d2free is increased, and it means that the recording can be performed in higher density and with higher reliability. Further, with respect to PR4, a practical Trellis code which sets d2free to 4 is known (TCPR4). Here, TCPR4 is a combination system of PR4 and the Trellis code.
There is known a theory in which the value of d2free can be increased by making coincidence between the null point of power density of codes and the null point of the transfer function of a transfer path, and the Trelllis code formed on the basis of the theory is called as MSN (Matched Spectral Null) code.
For example, in PR4, the transfer function becomes null at a DC component and a frequency component (so-called Nyquist frequency) of a half of a recording rate (1/Tc, Tc represents the time width (bit period) of one code bit). Accordingly, d2free can be increased by making one or both of the DC component of the code and the Nyquist frequency null.
Further, for example, in the partial response (1,1) (hereinafter abbreviated as PR1), the transfer function is null at the Nyquist frequency component. Accordingly, d2free can be increased by making null the Nyquist frequency component of the power density of the code.
Here, symbols xe2x80x9c+1xe2x80x9d and xe2x80x9cxe2x88x921xe2x80x9d are allocated to code bits xe2x80x9c1xe2x80x9d and xe2x80x9c0xe2x80x9d respectively, and the sum of all the symbols from a symbol at a start time point (start point) or an infinite past of a code sequence to a symbol at the current time point, that is, RDS (Running Digital Sum) is an index for estimating the above DC component. If RDS is limited to a value within a fixed range, it means that the DC component of the power density of the code becomes null.
As in the case of RDS, the sum of all the values obtained by multiplying the symbol xe2x80x9c+1xe2x80x9d or xe2x80x9cxe2x88x921xe2x80x9d allocated to a code bit by xe2x80x9cxe2x88x921xe2x80x9d every other bit from a start time point or infinite past to the current time point, that is, ADS (Alternating Digital Sum) is an index for estimating the Nyquist frequency component as described above. If ADS is limited to a value within a fixed range, it means that the Nyquist frequency component of the power density of the code becomes null.
When the transfer function has a DC component like PR1, it is generally required to make the DC component of the power density of the code null. That is, it is required to prevent a DC component from being contained in a code which is a recording signal, for example in order to prevent occurrence of an error due to fluctuation of a reference level when a code is detected from a reproduction signal by the Viterbi detection in magnetic recording/reproduction having differential characteristics in a reproducing system, and in order to prevent occurrence of variation of various error signals such as a tracking error signal, etc. in servo control of a disc device in recording/reproduction of an optical disc or a magnet optical disc.
Therefore, in 8/10 conversion code (Rate 8/10 code) adopted in digital audio tape recorders (DAT), DSV (Digital Sum Variation) which is the amplitude value of RDS (the maximum value of RDSxe2x80x94Minimum value of RDS) is made infinite so that the power density of the code has no DC component, and also DSV is reduced to as small a value as possible. Here, the smaller DSV is, the more the low frequency band component of the power density of the code is suppressed. The code which is subjected to DSV control is called as xe2x80x9cDS free codexe2x80x9d.
In EFM (Eight-to-Fourteen Modulation) used for compact disc (CD) players, although the complete DC free coding is not performed, the control is performed so that DSV is reduced as much as possible in order to suppress the low frequency band component of the power density thereof.
Further, in the case where the PRML system is applied, there occurs a problem in length of a path memory for the Viterbi detection operation. The path memory is a storage device for storing a temporary judgment value of the detection until the Viterbi detection result is settled, and it needs a length (storage capacity) proportional to the time interval until the detection result (decoding result) is settled.
The time interval until the Viterbi detection result is settled, that is, the length of the path memory is normally controlled by constructing codes so that the Quasi-Catastrophic sequence (hereinafter referred to as xe2x80x9cQC sequencexe2x80x9d) is nullified and also the maximum length of the minimum-distance error events is shortened as much as possible.
Here, the minimum-distance error events generally indicate error events caused by a sequence making d2free on detector Trellis. The QC sequence means two or more different paths whose squared euclidean distances are not accumulated on the Trellis diagram and thus exist (continue) infinitely. For example, when paths having state transitions of 111 . . . , 333 . . . , 555 . . . respectively on the Trellis diagram continue infinitely for a code sequence 101010 . . . , these three paths are called as QC sequences. Since the distance between the respective paths is not accumulated at any time and thus equal to zero, it cannot be judged which QC sequence of these sequences is right, that is, the path cannot be settled. Therefore, when a QC sequence occurs, the result of Viterbi detection cannot be settled.
When a device for performing the Viterbi detection is actually implemented, it is impossible to have a path memory having an infinite capacity, and also it is required from the viewpoint of cost, the size of occupation space (device scale), power consumption, etc. that the device has as short a path memory as possible. Therefore, the following manner of nullifying the QC sequence has been proposed.
That is, for example when the 8/10 code is applied to PR1, the QC sequence can be nullifying by restricting one continuous number of a data sequence before NRZI (Non Return to Zero Inverted).
Besides, so-called Tmin (the minimum continuous length of the same symbol) and Tmax (the maximum continuous length of the same symbol) of a code which is a recording signal is important as an index for estimating the performance of the code, and it is preferable that Tmax is as small as possible.
That is, for example, in the magnetic recording/reproduction, as Tmax is large, a problem occurs in deletion rate in an overwrite operation. Further, when an azimuth recording operation is carried out, cross talk from an adjacent track is intensified to deteriorate the quality of reproduced data. With respect to PLL (Phase Locked Loop), as Tmax is large, the amount of information to establish synchronization is reduced to cause malfunction.
In the above combination with PR4, an MSN code (Sectioned-MSN code) of 8/10 rate based on a method called as partitioning as one of MSN codes setting d2free to 4 has been proposed in L. Fredrickson, R. Karabed, J. Rae, P. Siegel, H. Thapar and R. Wood, xe2x80x9cImproved Trellis-Coding for Partial-Response Channelsxe2x80x9d, IEEE Transaction on Magnetics, Vol. 31, No. 2, March 1995, pp.1141-1148. The length of the path memory of this code can be shortened to a smaller value as compared with MSN codes of 8/10 rate which have been hitherto reported, for example, in U.S. Pat. No. 5,095,484 or H. Thapar, J. Rac, C. Shung, R. Karabed and P. Siegel, xe2x80x9cOn the performance of a Rate 8/10 Matched Spectral Null Code for Class-4 Partial responsexe2x80x9d, IEEE Transaction on Magnetics, Vol. 28, No. 5, September 1992, pp. 2883-2888.
Comparing PR1 and PR4, the transfer function of a high frequency band is more suppressed in PR1 than PR4, and thus emphasis of a high frequency band noise is reduced. Therefore, PR1 is more effective to high line densification. This has been already reported in H. Ino and Y. Shipuku, xe2x80x9c8/10 PR1ML for High Density and High Rate Tape Strage Systemsxe2x80x9d, IEEE Transaction on Magnetics, Vol. 31, No. 6, November 1995, pp.3036-3038, H. Ino, S. Higashino, and Y. Shinpuku, xe2x80x9cPerformance of Trellis-Coded Class-1 Partial responsexe2x80x9d, IEEE Transaction on Magnetics, Vol. 33, No. 5, September 1997, pp.2752-2754, etc.
The applicant of this application previously proposed a 16/20 MSN code which is a Trellis code having a conversion efficiency (coding rate) of 4/5 and aims to be applied to PR1 and further a partial response in which the transfer function has a null point at the Nyquist frequency (Japanese Laid-open patent Application No. Hei-9-64231). The power density of this code becomes null at the Nyquist frequency, and further it is null even in the case of direct current (DC). When this code is applied to PR1 (TCPR1), assuming that d2free when no coding is carried out is equal to 2, d2free can be set to 4. The maximum length of the minimum-distance error event is equal to 5 code length (one code length is equal to 20 bits), and the maximum continuous length of the same symbol is equal to 10.
In this case, the maximum length of the minimum-distance error event is equal to 5 code length, and thus the required length of the path memory is equal to about 5 code length. However, from the viewpoint of the scale, cost, etc. of the hardware, the length of the path memory is required to be further shortened.
The code after a Partitioned-MSN code which aims to be applied to PR4 is interleaved can be applied to not only PR4, but also PR1. This is because the power density of the code after the interleave is null not only in the case of DC, but also at the Nyquist frequency thereof, and further a mechanism for preventing occurrence of the QC sequence is applied to TCPR 1. Since the DC component of the power density is null, the code is a DC free code, and also since the Nyquist frequency component is null, d2free can be set to 4 for even TCPR1. Further, when the Partitioned-MSN code is applied, GTD (Generalized Truncation Depth) is equal to 40 bits, and it is extremely smaller than the 5 code length (100 bits) in the above 16/20 MSN code.
Here, GTD means the maximum length of the squared euclidean distance of pairs of paths which start from every common state as a start point until the squared euclidean distance reaches the squared free euclidean distance d2free (for example, 4 for the above Partitioned-MSN code). Wherein of these pairs of the paths starting from the common states, at least one of each pair is assumed to be a code sequence. GTD is used when the detector Trellis is timely varied, and it is used as an index indicating the needed length of the path memory as in the case of the maximum length of the minimum-distance error event.
However, in the case of TCPR1 based on the Partitioned-MSN code, if the same method as TCPR4, that is, the method described in L. Fredrickson, R. Karabed, J. Rae, P. Siegel, H. Thapar and R. Wood, xe2x80x9cImproved Trellis-coding for Partial-Response Channelsxe2x80x9d, IEEE Transactionon Magnetics, Vol. 31, No. 2, March 1995, pp 1141-1148 is used in the detection operation, there has been a problem that an extra state transition which does not correspond to the code sequence is unintentionally contained in the detector Trellis of TCPR1, and a part of it becomes a QC sequence.
Therefore, the applicant of this application previously proposed a method of effectively nullifying the QC sequence from the detector Trellis when the Partitioned-MSN code is applied to a partial response whose transfer function has a null point at the Nyquist frequency, in Japanese Laid-open Patent Application No. Hei-8-329376 or H. Ino, S. Higashino, and Y. Shinpuku, xe2x80x9cPerformance of Trellis-Coded Class-1 Partial Responsexe2x80x9d, IEEE Transaction on Magnetics, Vol. 33, No. 5, September 1997, pp. 2752-2754 described above. The maximum continuous length of the same symbol of the Partitioned-MSN code described above is set to 10.
However, the above method has problems that it needs additive processing of removing the QC sequence from the detector Trellis, and this disturbs the high-speed processing of the Viterbi detector. Further, it is preferable that the maximum continuous length of the same symbol of the Partitioned-MSN code is as small as possible.
FIG. 1 shows the construction of a conventional encoder.
First, a 16-bit data word is input to an encoding circuit 101. The encoding circuit 101 is designed to associate the 16-bit data word to a 20-bit code word, and it serves to convert the input data word to the code word. A register 102 stores the state of the end point in a state transition diagram to generate the code word. The output of the register 102 is fed back to the encoding circuit 101, and the encoding circuit 101 generates a code word on the basis of the data word and the state of the end point in a previous code word. The 20-bit code word and the state of the end point of the code word are supplied to a parallel/serial converter 103, and the parallel/serial converter 103 converts the supplied data to serial data and outputs the serial data thus converted.
FIG. 2 shows the construction of a conventional decoder. When a 20-bit code word is input, a decoding circuit 111 converts the 20-bit code word thus input to a 16-bit data word and outputs the 16-bit data word thus converted.
However, in the encoder of FIG. 1, the present code word cannot be generated unless the state of the end point in the previous code word is settled, so that the processing speed of the encoder cannot be enhanced.
The present invention has been implemented in view of such a situation, and has an object to enable enhancement of the processing speed of an encoder for generating an MSN code which is applicable to a partial response whose transfer polynomial has a null point at the Nyquist frequency.
Further, the present invention has another object to supply an MSN code in which the maximum continuous length of the same symbol is small.
According to an aspect of the present invention, there is provided with an encoding method for encoding m-bit data to an n-bit code, which is characterized in that: the n-bit code is generated according to a finite state transition diagram representing the restriction of ADS and RDS received by a code sequence; two states contained in a state assembly set as start points of the n-bit code in the finite state transition diagram exist at symmetrical positions with respect to the center point of the finite state transition diagram, at symmetrical positions with respect to the ADS axis passing through the center point of the finite state transition diagram or at the symmetrical positions with respect to the RDS axis passing the center point of the finite state transition diagram; the m-bit data are encoded to an n-bit code word having as a start point a predetermined state contained in a state assembly set as start points of the code; and an n-bit code word having as a start point another state contained in a state assembly set as start points by the code is obtained by further converting the encoded code word.
According to another aspect of the present invention, there is provided an encoding device for encoding m-bit data to an n-bit code, characterized by comprising: encoding means for converting an input m-bit data word to an n-bit code word having as a start point a predetermined state contained in a state assembly set as start points of the code; code word examining means for examining the state of the end point (end-state) of a code word and the type of the code word on the basis of the code word supplied from the encoding means; end point state converting means for converting the state of the end point supplied from the code word examining means to the state of the end point output from the code word converting means; storing means for storing the end-point state output from the end-point state converting means by the amount corresponding to one code word, and outputting the state of the start point of a code word which will be next output from the code word converting means; and code word converting means for converting an n-bit code word having as a start point a predetermined state contained in a state assembly set as start points by the code supplied from the encoding means to an n-bit code word having as a start point another state contained in a state assembly set as start points of the code.
According to further aspect of the present invention, there is provided a decoding method for decoding an n-bit code to m-bit data, characterized in that: the n-bit code is generated according to a finite state transition diagram representing the restriction of ADS and RDS received by a code sequence; two states contained in a state assembly set as start points of the n-bit code in the finite state transition diagram exist at symmetrical positions with respect to the center point of the finite state transition diagram, at symmetrical positions with respect to the ADS axis passing through the center point of the finite state transition diagram or at the symmetrical positions with respect to the RDS axis passing the center point of the finite state transition diagram; an n-bit code word having as a start point any state contained in a state assembly set as start points of the code is converted to another n-bit code word having as a start point a predetermined state contained in a state assembly set as start points of the code; and the m-bit data word is obtained by decoding the converted code word.
According to a yet further aspect of the present invention, there is provided a decoding device for decoding an n-bit code to m-bit data, characterized by comprising: code word examining means for examining the state of a start point of an input n-bit code word and the type thereof; code word converting means for converting an n-bit code word having as a start point any state contained in a state assembly set as start points of the input code to another n-bit code word having as a start point a predetermined state contained in a state assembly set as start points of the code; and decoding means for decoding a code word converted by the code word converting means to the m-bit data word.
According to a still further aspect of the present invention, there is provided a supply medium in which an n-bit code obtained by encoding m-bit data is recorded, characterized in that the n-bit code is generated according to a finite state transition diagram representing the restriction of ADS and RDS received by a code sequence; two states contained in a state assembly set as start points of the n-bit code in the finite state transition diagram exist at symmetrical positions with respect to the center point of the finite state transition diagram, at symmetrical positions with respect to the ADS axis passing through the center point of the finite state transition diagram, or at the symmetrical positions with respect to the RDS axis passing the center point of the finite state transition diagram.